package psn.zjk.common.algorithm.lru;

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @USER white
 * @DATETIME 2021/1/8 19:39
 */
public class Main {


    public static void main(String[] args) throws IOException {

        BufferedInputStream bi = new BufferedInputStream(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(bi));

        String size = br.readLine();
        int sizea = Integer.parseInt(size);
        Lru lru = new Lru(sizea);
        String line = null;
        while ((line = br.readLine()) != null) {
            try {
                String[] s = line.split(" ");
                if (s.length == 3 && s[0].charAt(0) == 'p') {
                    int k = Integer.parseInt(s[1]);
                    int v = Integer.parseInt(s[2]);
                    lru.put(k, v);
                } else if (s.length == 2 && s[0].charAt(0) == 'g') {
                    int k = Integer.parseInt(s[1]);
                    System.out.println(lru.get(k));
                }
            } catch (Exception e) {
                throw new RuntimeException("参数不对");
            }
        }


    }

    static class Lru {
        private Map<Integer, Integer> map;
        private LinkedList<Integer> list;
        private int size;

        public Lru(int size) {
            this.map = new HashMap<>();
            list = new LinkedList<Integer>();
            this.size = size;
        }


        public void put(int key, int value) {
            if (!map.containsKey(key)) {
                if (list.size() >= size) {
                    Integer integer = list.removeLast();
                    System.out.println("移除" + integer);
                    map.remove(integer);
                }
                list.addFirst(key);
            }
            map.put(key, value);

        }


        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            } else {
                list.removeFirstOccurrence(key);
                list.addFirst(key);
            }
            return map.get(key);
        }
    }
}
